home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 297_01 / prparse.c < prev    next >
C/C++ Source or Header  |  1980-01-01  |  9KB  |  397 lines
  1. /* prparse.c */
  2. /* recursive descent parser for lisp-like syntax 
  3.  * Makes use of scan.
  4.  */
  5.  
  6. #include <stdio.h>
  7. #include <ctype.h>
  8. #include "prtypes.h"
  9. #include "prlex.h"
  10.  
  11.  
  12. #define TOOMANYVARS "too many vars"
  13. #define PARSERRMSG "parsing error"
  14. #define SCAN_ERRMSG "scan error"
  15. #define EOFINEXP "EOF in expression"
  16. #define VARSTOOLONG "the total length of the variable names is too long"
  17. #define BADINT "bad integer"
  18. #ifdef REAL
  19. #define BADREAL "bad real"
  20. #else
  21. #define NOREALS "no reals in this version"
  22. #endif
  23. #define UNEXPECTED "unexpected symbol"
  24. #define NONLISTARG "expected a list"
  25. #define CLOSEBEXPECTED " ) expected"
  26.  
  27.  
  28. extern char *Read_buffer;/* pralloc.c */
  29. extern char *Print_buffer;/* pralloc.c */
  30. extern char *parserr();/* error.c */
  31. extern atom_ptr_t Nil;
  32. extern unsigned int Inp_linecount;
  33. extern int scan();
  34.  
  35. #ifdef CHARACTER
  36. extern CHAR Char_scanned;
  37. #endif
  38.  
  39. varindx Nvars;
  40.  
  41. static char *VarNames[MAX_VAR]; /*names of vars used to attribute offsets */
  42. char *Var2Names[MAX_VAR];/* copy of VarNames used to display solution */
  43. static char VarNameBuff[VARBUFSIZE]; /* used to allocate names */
  44. static char *Varbufptr; /* moves along VarNameBuff */
  45. static int Last_token;  /* used by parse so as to avoid lookahead */
  46.  
  47. /**********************************************************************
  48.             read_list()
  49. Main function of this file.
  50. Reads a list and complains if not a list (and returns NULL).
  51. Returns node_ptr_t to list parsed.
  52. Updates VarNames, Nvars.
  53.  **************************************************************************/
  54. node_ptr_t read_list(status)
  55. int status;
  56. {
  57. void ini_parse();
  58. node_ptr_t nodeptr, get_node(), parse();
  59.  
  60. ini_parse();
  61. nodeptr = get_node(status);
  62.  
  63. if(parse(FALSE, status, nodeptr) == NULL)
  64.    return(NULL);
  65.  
  66. if(NODEPTR_TYPE(nodeptr) != PAIR)
  67.    {
  68.    errmsg(NONLISTARG);
  69.    return(NULL);
  70.    }
  71.  
  72.  
  73. return(nodeptr);
  74. }
  75.  
  76. /****************************************************************************
  77.             ini_parse()
  78.  ****************************************************************************/
  79. void ini_parse()
  80. {
  81. register int i;
  82.  
  83. for(i = 0; i < MAX_VAR; i++)
  84.    VarNames[i] = NULL;
  85.  
  86. Varbufptr = VarNameBuff;
  87. Nvars = 0;
  88. }
  89.  
  90.  
  91. /****************************************************************************
  92.             parse()
  93.  Returns NULL if parse failed.
  94.  ****************************************************************************/
  95.  
  96. node_ptr_t parse(use_Last_token, status, nodeptr)
  97. int use_Last_token, /* a flag: use the global, dont start with a scan */
  98. status; /* PERMANENT OR DYNAMIC etc */
  99. node_ptr_t nodeptr;/* *nodeptr gets modified by this function*/
  100. {
  101. atom_ptr_t intern();
  102. real_ptr_t find_real();
  103. string_ptr_t find_string();
  104. varindx find_offset();
  105. pair_ptr_t the_list, parse_list();
  106. int toktype, next_token;
  107. objtype_t type;
  108.  
  109. if(use_Last_token == FALSE)
  110.    do{    /* skip spaces */
  111.    toktype = scan();
  112.  
  113.    if(toktype == EOF)
  114.       return(NULL);
  115.  
  116.    }
  117. while(toktype < 33 && isspace(toktype));
  118. else 
  119.    toktype = Last_token;
  120. switch(toktype)
  121. {
  122. case TOKEN_INT:
  123.    type = INT;
  124.    if(!sscanf(Read_buffer, "%ld", &(NODEPTR_INT(nodeptr))))
  125.       return (node_ptr_t)parserr(BADINT);
  126.    break;    
  127.  
  128. case TOKEN_REAL:
  129. #ifdef REAL
  130.    type = REAL;
  131.    NODEPTR_REALP(nodeptr) = find_real(Read_buffer, status);
  132.    break;
  133. #else
  134.    return(node_ptr_t) parserr(NOREALS);
  135. #endif
  136.  
  137. case TOKEN_ATOM:
  138.    type = ATOM;
  139.    NODEPTR_ATOM(nodeptr) = intern(Read_buffer);
  140.    break;
  141.  
  142. case TOKEN_VAR:
  143.    type = VAR;
  144.    if((NODEPTR_OFFSET(nodeptr) = find_offset(Read_buffer)) == -1)
  145.       {
  146.       return(NULL);
  147.       }
  148.    break;
  149.  
  150. case TOKEN_STRING:
  151.    type = STRING;
  152.    NODEPTR_STRING(nodeptr) = find_string(Read_buffer, status);
  153.    break;
  154.  
  155. #ifdef CHARACTER
  156. case TOKEN_CHAR:
  157.    type = CHARACTER;
  158.    NODEPTR_CHARACTER(nodeptr) = Char_scanned;
  159.    break;
  160. #endif
  161. case SCAN_ERR:
  162.    return (node_ptr_t)parserr(UNEXPECTED);
  163.  
  164. case '(':
  165.    next_token = scan();
  166.  
  167.    if(next_token == ')')
  168.       {
  169.       type = ATOM;
  170.       NODEPTR_ATOM(nodeptr) = Nil;
  171.       break;
  172.       }
  173.    else
  174.       type = PAIR;
  175.    Last_token = next_token;
  176.    the_list = parse_list(status);
  177.  
  178.    if(the_list == NULL)
  179.       {
  180.       return(NULL);
  181.       }
  182.  
  183.    NODEPTR_PAIR(nodeptr) = the_list;
  184.    break;
  185.  
  186. case EOF:
  187.    return((node_ptr_t)parserr(EOFINEXP));
  188.  
  189. default:
  190.    return (node_ptr_t)parserr(UNEXPECTED);
  191. } /* end switch */
  192.  
  193. NODEPTR_TYPE(nodeptr) = type;
  194. return(nodeptr);
  195. }
  196.  
  197. /***************************************************************************
  198.             getvarname()
  199. ****************************************************************************/
  200. char *getvarname(s)
  201. char *s;
  202. {
  203. char *ret;
  204. int how_long;
  205.  
  206. how_long = strlen(s) + 1;
  207. ret = Varbufptr;
  208.  
  209. if(how_long >= (VarNameBuff  + VARBUFSIZE) -ret )
  210.    {
  211.    return parserr(VARSTOOLONG);
  212.    }
  213. else
  214.    strcpy(ret, s);
  215. Varbufptr += how_long;
  216. return(ret);
  217. }
  218.  
  219. /******************************************************************
  220.             copy_varnames()
  221. Keep a copy of the names of the variables for an answer to a query.
  222.  *******************************************************************/
  223. copy_varnames()
  224. {
  225. int i;
  226. char *get_string();
  227.  
  228. for(i = 0; i < Nvars; i++)
  229.    {
  230.    Var2Names[i] = get_string((my_alloc_size_t)(strlen(VarNames[i]) + 1), DYNAMIC);
  231.    strcpy(Var2Names[i], VarNames[i]);
  232.    }
  233. }
  234.  
  235. /****************************************************************************
  236.             find_offset()
  237. Finds an offset for a variable.
  238.  ****************************************************************************/
  239. varindx find_offset(s)
  240. char *s;
  241. {
  242. int i;
  243. char *the_name;
  244. if(!strcmp(s, "_"))
  245.    {
  246.  
  247.    if(Nvars >= MAX_VAR)
  248.       {
  249.       parserr(TOOMANYVARS);
  250.       return( -1);
  251.       }
  252.    else
  253.       VarNames[Nvars] = getvarname(s);
  254.    Nvars++;
  255.    return((Nvars - 1) * sizeof(struct subst));
  256.    }
  257.  
  258. for(i = 0; i < Nvars; i++)
  259.    {
  260.    if(VarNames[i] == NULL)break;
  261.    if(!strcmp(s, VarNames[i]))
  262.       {
  263.       return(sizeof(struct subst) * i);
  264.       }
  265.    }
  266.  
  267. if(Nvars == MAX_VAR)
  268.    {
  269.    parserr(TOOMANYVARS);
  270.    return(-1);
  271.    }
  272.  
  273. if((the_name = getvarname(s)) == NULL)
  274.    return(-1);
  275.  
  276. VarNames[i] = the_name; 
  277. Nvars++;
  278. return(sizeof(struct subst) * i);/* do this multiplication once now 
  279.                             rather than at runtime*/
  280.  
  281. }
  282.  
  283. #ifdef REAL
  284. /****************************************************************************
  285.             find_real()
  286. Find a real corresponding to a string.
  287.  ****************************************************************************/
  288.  
  289. real_ptr_t find_real(s, status)
  290. char *s;
  291. {
  292. double atof();
  293. real_ptr_t dp, get_real();
  294.  
  295.  
  296. dp = get_real(status);
  297. *dp = atof(s);
  298.  /* on error return (real_ptr_t)parserr(BADREAL); */
  299. return(dp);
  300. }
  301. #endif
  302.  
  303. /****************************************************************************
  304.             find_string()
  305.  Allocate a string for an input.
  306.  ****************************************************************************/
  307. string_ptr_t find_string(s, status)
  308. char *s;
  309. int status;
  310. {
  311. string_ptr_t s1, get_string();
  312.  
  313. if(status == PERMANENT)
  314.    status = PERM_STRING;
  315. s1 = get_string((my_alloc_size_t)(strlen(s) + 1), status);
  316. strcpy(s1, s);
  317. return(s1);
  318. }
  319.  
  320.  
  321. /****************************************************************************
  322.             parse_list()
  323.  Called by parse.
  324.  ****************************************************************************/
  325.  
  326. pair_ptr_t parse_list(status)
  327. {
  328. pair_ptr_t the_list, pairptr, get_pair();
  329. node_ptr_t headptr, tailptr;
  330.  
  331. int next_token;
  332.  
  333. the_list = get_pair(status);
  334. pairptr = the_list;
  335.  
  336.    do{
  337.    headptr = &(pairptr->head);
  338.    tailptr = &(pairptr->tail);
  339.  
  340.    if(parse(TRUE, status, headptr) == NULL)
  341.       {    
  342.       return(NULL);
  343.       }
  344.    else
  345.       next_token = scan();
  346.  
  347.    if(next_token == ')')
  348.       {
  349.       NODEPTR_TYPE(tailptr) = ATOM;
  350.       NODEPTR_ATOM(tailptr) = Nil;
  351.       return(the_list);
  352.       }
  353.  
  354.    if(next_token == CONS)
  355.       {
  356.       if(!parse(FALSE, status, tailptr))
  357.      {
  358.      return(NULL);
  359.      }
  360.       if(scan() != ')')
  361.      {
  362.      return (pair_ptr_t)parserr(CLOSEBEXPECTED);/* move past